{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum Circular Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #divide-and-conquer #dynamic-programming #monotonic-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #分治 #动态规划 #单调队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubarraySumCircular"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形子数组的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的<strong>环形整数数组</strong>&nbsp;<code>nums</code>&nbsp;，返回<em>&nbsp;<code>nums</code>&nbsp;的非空 <strong>子数组</strong> 的最大可能和&nbsp;</em>。</p>\n",
    "\n",
    "<p><strong>环形数组</strong><em>&nbsp;</em>意味着数组的末端将会与开头相连呈环状。形式上， <code>nums[i]</code> 的下一个元素是 <code>nums[(i + 1) % n]</code> ， <code>nums[i]</code>&nbsp;的前一个元素是 <code>nums[(i - 1 + n) % n]</code> 。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 最多只能包含固定缓冲区&nbsp;<code>nums</code>&nbsp;中的每个元素一次。形式上，对于子数组&nbsp;<code>nums[i], nums[i + 1], ..., nums[j]</code>&nbsp;，不存在&nbsp;<code>i &lt;= k1, k2 &lt;= j</code>&nbsp;其中&nbsp;<code>k1 % n == k2 % n</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-2,3,-2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>从子数组 [3] 得到最大和 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,-3,5]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>从子数组 [5,5] 得到最大和 5 + 5 = 10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,-2,2,-3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-3 * 10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 3 * 10<sup>4</sup></code>​​​​​​​</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-circular-subarray](https://leetcode.cn/problems/maximum-sum-circular-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-circular-subarray](https://leetcode.cn/problems/maximum-sum-circular-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-2,3,-2]', '[5,-3,5]', '[-3,-2,-3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        curMin = curMax = globalMin = globalMax = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            curMin = min(curMin+nums[i],nums[i])\n",
    "            curMax = max(curMax+nums[i],nums[i])\n",
    "            globalMin = min(globalMin, curMin)\n",
    "            globalMax = max(globalMax, curMax)\n",
    "        \n",
    "        total = sum(nums)\n",
    "        return max(globalMax, total-globalMin) if total != globalMin else globalMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total, maxSum, curMax, minSum, curMin = 0, float('-inf'), 0, float('inf'), 0\n",
    "        for a in A:\n",
    "            curMax = max(curMax + a, a)\n",
    "            maxSum = max(maxSum, curMax)\n",
    "            curMin = min(curMin + a, a)\n",
    "            minSum = min(minSum, curMin)\n",
    "            total += a\n",
    "        return max(maxSum, total - minSum) if maxSum > 0 else maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: 'List[int]') -> 'int':\n",
    "        sum_ = sum(A)\n",
    "        \n",
    "        csum = -float(\"inf\")\n",
    "        bsum = float(\"inf\")\n",
    "        \n",
    "        tmp_sum = 0\n",
    "        tmp_sumb = 0\n",
    "        for n in A:\n",
    "            tmp_sum += n\n",
    "            tmp_sumb += n\n",
    "            bsum = min(bsum, tmp_sumb)\n",
    "            if tmp_sumb > 0:\n",
    "                tmp_sumb = 0\n",
    "            csum = max(csum, tmp_sum)\n",
    "            if tmp_sum < 0:\n",
    "                tmp_sum = 0\n",
    "        return max(csum, sum_ - bsum if sum_ != bsum else -float(\"inf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def kadane(nums):\n",
    "            result = cur = float('-inf')\n",
    "            for num in nums:\n",
    "                cur = max(cur, 0) + num\n",
    "                result = max(result, cur)\n",
    "            return result\n",
    "\n",
    "        max_A = max(A)\n",
    "        if max_A < 0:\n",
    "            return max_A\n",
    "\n",
    "        result1 = kadane(A)\n",
    "        result2 = sum(A) + kadane([-num for num in A])\n",
    "        return max(result1, result2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def kadane(nums):\n",
    "            result = cur = float('-inf')\n",
    "            for num in nums:\n",
    "                cur = max(cur, 0) + num\n",
    "                result = max(result, cur)\n",
    "            return result\n",
    "\n",
    "        max_A = max(A)\n",
    "        if max_A < 0:\n",
    "            return max_A\n",
    "\n",
    "        result1 = kadane(A)\n",
    "        result2 = sum(A) + kadane([-num for num in A])\n",
    "        return max(result1, result2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        ans = A[0]\n",
    "        accu = 0\n",
    "        cur_max = 0\n",
    "        for n in A:\n",
    "            accu += n\n",
    "            cur_max = max(cur_max, 0) + n\n",
    "            ans = max(ans, cur_max)\n",
    "\n",
    "        if len(A) < 2:\n",
    "            return ans\n",
    "\n",
    "        min_ans = A[1]\n",
    "        cur_min = 0\n",
    "        for i in range(1, len(A)-1):\n",
    "            cur_min = min(cur_min, 0) + A[i]\n",
    "            min_ans = min(min_ans, cur_min)\n",
    "        return max(ans, accu-min_ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "#         l = len(A)\n",
    "#         A = A + A\n",
    "#         ans = A[0]\n",
    "#         s = [0] * (2 * l)\n",
    "#         q = [0]\n",
    "#         for i in range(1, 2 * l):\n",
    "#             s[i] = s[i - 1] + A[i - 1]\n",
    "#             while q and q[0] < i - l:\n",
    "#                 q.pop(0)\n",
    "#             ans = max(ans, s[i] - s[q[0]])\n",
    "#             while q and s[q[-1]] > s[i]:\n",
    "#                 q.pop()\n",
    "#             q.append(i)\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        result = 0\n",
    "        curr_max = 0\n",
    "        result_max = 0\n",
    "        \n",
    "        # 分两种情况\n",
    "        # 一种为没有跨越边界的情况，一种为跨越边界的情况 没有跨越边界的情况直接求子数组的最大和即可\n",
    "        for num in A:\n",
    "            curr_max += num\n",
    "            if curr_max <= 0:\n",
    "                curr_max = 0\n",
    "            if curr_max > result_max:\n",
    "                result_max = curr_max\n",
    "                \n",
    "        # 考虑全部为负数的情况\n",
    "        if result_max == 0:\n",
    "            result = max(A)\n",
    "            return result\n",
    "        \n",
    "        # 跨越边界的情况可以对数组求和再减去无环的子数组的最小和，即可得到跨越边界情况下的子数组最大和\n",
    "        curr_min = 0\n",
    "        result_min = 0\n",
    "        for num in A:\n",
    "            curr_min += num\n",
    "            if curr_min >= 0:\n",
    "                curr_min = 0\n",
    "            if curr_min < result_min:\n",
    "                result_min = curr_min\n",
    "        \n",
    "        result = max(result_max, sum(A)-result_min)\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# [-2,4,-5,4,-5,9,4]\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        if len(A) == 0:\n",
    "            return 0;\n",
    "        if len(A) == 1:\n",
    "            return A[0]\n",
    "            \n",
    "        maxSumWithoutLoop = self.maxSubarraySum(A)\n",
    "        minSumWithLoop = self.minSubarraySum(A[1:-1])\n",
    "        return max(maxSumWithoutLoop, sum(A) - minSumWithLoop)\n",
    "\n",
    "    def maxSubarraySum(self, A: List[int]) -> int:\n",
    "        prev = A[0]\n",
    "        result = prev\n",
    "        for i in range(1, len(A)):\n",
    "            if prev > 0 :\n",
    "                prev += A[i]\n",
    "            else:\n",
    "                prev = A[i]\n",
    "            result = max(result, prev)\n",
    "        return result\n",
    "\n",
    "    def minSubarraySum(self, A:List[int])-> int:\n",
    "        if len(A) == 0:\n",
    "            return 0\n",
    "        prev = A[0]\n",
    "        result = prev\n",
    "        for i in range(1, len(A)):\n",
    "            if prev > 0:\n",
    "                prev = A[i]\n",
    "            else:\n",
    "                prev += A[i]\n",
    "            result = min(result, prev)\n",
    "        return min(result, 0)\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        total, max_s, min_s, max_cur, min_cur = 0, -float('INF'), float('INF'), 0, 0 \n",
    "        for item in A:\n",
    "            total += item\n",
    "            max_cur = max(item, item+max_cur)\n",
    "            max_s = max(max_s, max_cur)\n",
    "            min_cur = min(item, item+min_cur)\n",
    "            min_s = min(min_s, min_cur)\n",
    "        return max(max_s, total-min_s) if max_s>0 else max_s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        lg = len(A)\n",
    "        cur = ans = float('-inf')\n",
    "        # 1个为间隔的\n",
    "        for i in range(lg):\n",
    "            cur = A[i] + max(cur,0)\n",
    "            ans = max(cur,ans)\n",
    "        \n",
    "        # 2个为间隔的\n",
    "        sum_right = [None]*lg\n",
    "        sum_right[-1] = A[-1]\n",
    "        for i in range(lg-2,-1,-1):\n",
    "            sum_right[i] = sum_right[i+1]+ A[i]\n",
    "\n",
    "\n",
    "        # 倒序找最大\n",
    "        max_right = [None]*lg\n",
    "        max_right[-1] = sum_right[-1]\n",
    "        for i in range(lg-2,-1,-1):\n",
    "            max_right[i] = max(max_right[i+1],sum_right[i])\n",
    "\n",
    "        left_sum = 0\n",
    "        for i in range(lg-2):\n",
    "            left_sum += A[i]\n",
    "            ans = max(ans,left_sum + max_right[i+2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "        s = A[0]\n",
    "        res = A[0]\n",
    "        extend = A + A\n",
    "        #print(extend)\n",
    "        length = len(A)\n",
    "        start = 0\n",
    "        for i in range(1, length * 2):\n",
    "            if i - start >= length and s >= 0:\n",
    "                ns = nmin = 0\n",
    "                for i in range(length * 2):\n",
    "                    ns = min(extend[i], ns + extend[i])\n",
    "                    nmin = min(nmin, ns)\n",
    "                return s - nmin\n",
    "            elif s < 0:\n",
    "                start = i\n",
    "                s = extend[i]\n",
    "            else:\n",
    "                s += extend[i]\n",
    "            res = max(res, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, A: List[int]) -> int:\n",
    "\n",
    "        def max_nums(nums):\n",
    "            dp = [0]*len(nums)\n",
    "            dp[0] = nums[0]\n",
    "            max_value = nums[0]\n",
    "\n",
    "            for i in range(1, len(nums)):\n",
    "                dp[i] = max(dp[i - 1] + nums[i], nums[i])\n",
    "                max_value = max(dp[i], max_value)\n",
    "            \n",
    "            return max_value\n",
    "        def min_nums(nums):\n",
    "            dp = [0]*len(nums)\n",
    "            dp[0] = nums[0]\n",
    "            min_value = nums[0]\n",
    "\n",
    "            for i in range(1, len(nums) - 1):\n",
    "                dp[i] = min(dp[i - 1] + nums[i], nums[i])\n",
    "                min_value = min(dp[i], min_value)\n",
    "            \n",
    "            return min_value\n",
    "        if len(A) == 0:\n",
    "            return None\n",
    "\n",
    "        if len(A) == 1:\n",
    "            return A[0]\n",
    "        \n",
    "        return max(max_nums(A), sum(A) - min_nums(A))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        pre, max_sum = nums[0], nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            cur = max(pre + nums[i], nums[i])\n",
    "            max_sum = max(max_sum, cur)\n",
    "            pre = cur\n",
    "        if max_sum < 0:\n",
    "            return max_sum\n",
    "        pre, min_sum = nums[0], nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            cur = min(pre + nums[i], nums[i])\n",
    "            min_sum = min(min_sum, cur)\n",
    "            pre = cur\n",
    "        \n",
    "        return max(max_sum, sum(nums) - min_sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        #找到最大子数组和，最小子数组和，结果为max(最大子数组和，总和-最小子数组和)\n",
    "        maa = mii = ma = mi = s = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            ma = max(nums[i]+ma,nums[i])\n",
    "            mi = min(nums[i]+mi,nums[i])\n",
    "            maa = max(ma,maa)\n",
    "            mii = min(mii,mi)\n",
    "            s += nums[i]\n",
    "        print(maa)\n",
    "        print(mii)\n",
    "        if s == mii:\n",
    "            return maa\n",
    "        return max(maa,s-mii)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        minSum = maxSum = nums[0]\n",
    "        preMin, preMax = inf, -inf\n",
    "        total = 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            preMin = min(preMin + num, num)\n",
    "            preMax = max(preMax + num, num)\n",
    "            minSum, maxSum = min(minSum, preMin), max(maxSum, preMax)\n",
    "        if minSum == total: return maxSum\n",
    "        return max(maxSum, total - minSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        def ka(gen):\n",
    "            ans = cur = -1000000000\n",
    "            for x in gen:\n",
    "                cur = max(cur, 0) + x\n",
    "                ans = max(ans, cur)\n",
    "            print(ans)\n",
    "            return ans\n",
    "        s = sum(nums)\n",
    "        ans = ka(nums)\n",
    "        ans = max(ans, s + ka([-nums[i] for i in range(len(nums) - 1)]))\n",
    "        ans = max(ans, s + ka([-nums[i] for i in range(1, len(nums))]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        nums_sum_max = nums[0]\n",
    "        tmp = nums[0]\n",
    "        for n in nums[1:]:\n",
    "            tmp = max(tmp+n, n)\n",
    "            nums_sum_max = max(tmp, nums_sum_max)\n",
    "        print(nums_sum_max)\n",
    "\n",
    "        nums_sum_min = 0\n",
    "        tmp = 0\n",
    "        for n in nums[:-1]:\n",
    "            tmp = min(tmp + n, n)\n",
    "            nums_sum_min = min(nums_sum_min, tmp)\n",
    "        print(nums_sum_min)\n",
    "\n",
    "        return max(sum(nums)-nums_sum_min, nums_sum_max)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        leftMax = [0] * n\n",
    "        # 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况\n",
    "        leftMax[0], leftSum = nums[0], nums[0] \n",
    "        pre, res = nums[0], nums[0]\n",
    "        for i in range(1, n):\n",
    "            pre = max(pre + nums[i], nums[i])\n",
    "            res = max(res, pre)\n",
    "            leftSum += nums[i]\n",
    "            leftMax[i] = max(leftMax[i - 1], leftSum)\n",
    "        # 从右到左枚举后缀，固定后缀，选择最大前缀\n",
    "        rightSum = 0\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            rightSum += nums[i]\n",
    "            res = max(res, rightSum + leftMax[i - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        glo_max = nums[0]\n",
    "        glo_min = nums[0]\n",
    "        l = len(nums)\n",
    "        pre_max = nums[0]\n",
    "        pre_min = nums[0]\n",
    "        s = nums[0]\n",
    "        for n in nums[1:]:\n",
    "            s += n\n",
    "            pre_max = max(pre_max+n,n)\n",
    "            pre_min = min(pre_min+n,n)\n",
    "            glo_max = max(glo_max, pre_max)\n",
    "            glo_min = min(glo_min, pre_min)\n",
    "        return max(glo_max,s-glo_min) if glo_max > 0 else glo_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        pmi, pmx = 0, -inf\n",
    "        ans, s, smi = -inf, 0, inf\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            ans = max(ans, s - pmi)\n",
    "            smi = min(smi, s - pmx)\n",
    "            pmi = min(pmi, s)\n",
    "            pmx = max(pmx, s)\n",
    "        return max(ans, s - smi)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        leftMax = [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        leftSum = nums[0]\n",
    "        cur = nums[0]\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if cur < 0:\n",
    "                cur = nums[i]\n",
    "            else:\n",
    "                cur = nums[i] + cur\n",
    "            leftSum += nums[i]\n",
    "            leftMax[i] = max(leftMax[i-1], leftSum)\n",
    "            res = max(res, cur)\n",
    "        rightSum = 0\n",
    "        for i in range(n-1, 1, -1):\n",
    "            rightSum += nums[i]\n",
    "            res = max(rightSum + leftMax[i-1], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def num_max(nums):\n",
    " \n",
    "            dp = [0] * len(nums)\n",
    "            dp[0] = nums[0]\n",
    "\n",
    "            dp_min = [0] * len(nums)\n",
    "\n",
    "            for i in range(1,len(nums)):\n",
    "                if dp[i-1]+nums[i]>nums[i]:\n",
    "                    dp[i] = dp[i-1]+nums[i]\n",
    "                 \n",
    "                else:\n",
    "                    dp[i] = nums[i]\n",
    "    \n",
    "            for i in range(1,len(nums)):\n",
    "                if dp_min[i-1]+nums[i]<nums[i]:\n",
    "                    dp_min[i] = dp_min[i-1]+nums[i]\n",
    "                 \n",
    "                else:\n",
    "                    dp_min[i] = nums[i]\n",
    "            return max(dp),min(dp_min)\n",
    "        \n",
    "        d1,dp_min = num_max(nums)\n",
    "\n",
    "        return max(d1,sum(nums)-dp_min)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        nums_max = nums.copy()\n",
    "        nums_min = nums.copy()\n",
    "        for i in range(1,len(nums)):\n",
    "            nums_max[i] += max(nums_max[i-1],0)\n",
    "            nums_min[i] = min(nums_min[i],nums_min[i-1] + nums[i])\n",
    "        if min(nums_min) == sum(nums):return max(nums_max)\n",
    "        return max(max(nums_max),sum(nums)-min(nums_min))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp1 = [-inf for _ in range(n)]\n",
    "        dp2 = [inf for _ in range(n)]\n",
    "\n",
    "        # case 1\n",
    "        dp1[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if dp1[i-1]>0:\n",
    "                dp1[i] = dp1[i-1]+nums[i]\n",
    "            else:\n",
    "                dp1[i] = nums[i]\n",
    "        \n",
    "        # case 2\n",
    "        dp2[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if dp2[i-1]>0:\n",
    "                dp2[i] = nums[i]\n",
    "            else:\n",
    "                dp2[i] = dp2[i-1]+nums[i]\n",
    "        \n",
    "        sum_all = sum(nums)\n",
    "        dp1_max = max(dp1)\n",
    "        dp2_min = min(dp2)\n",
    "        \n",
    "        if dp2_min==sum_all: return dp1_max # 注意：case2中需要满足两边待求和最大子数组不能为空，即dp2_min所对应的不能是整个数组！！ 即 dp2_min!=sum_all\n",
    "\n",
    "        return max(dp1_max, sum_all-dp2_min)\n",
    "\n",
    "        ## 思路：分成两种情况：\n",
    "        ## case 1：同前一题，dp[i]找到和最大子数组\n",
    "        ## case 2；当和最大子数组在跨越首尾的时候，和最大子数组 等价于 nums总和减去最小中间子数组！！\n",
    "        ## 易错：case2中需要满足待求和最大子数组不能为空，即dp2不能是整个数组！！\n",
    "\n",
    "\n",
    "\n",
    "        # sum,preMax,maxRes,preMin,minRes = nums[0],nums[0],nums[0],nums[0],nums[0]\n",
    "        # for i in range(1,len(nums)):\n",
    "        #     preMax = max(preMax+nums[i], nums[i])\n",
    "        #     maxRes = max(maxRes, preMax)\n",
    "        #     preMin = min(preMin+nums[i], nums[i])\n",
    "        #     minRes = min(minRes, preMin)\n",
    "        #     sum+=nums[i]\n",
    "        \n",
    "        # if maxRes<0: return maxRes\n",
    "        # else:\n",
    "        #     return max(maxRes, sum-minRes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # sum_list = [0]\n",
    "        # for i in nums:\n",
    "        #     sum_list.append(sum_list[-1] + i)\n",
    "        \n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i,n+i):\n",
    "        #         if j<n:\n",
    "        #             sum_value = sum_list[j+1] - sum_list[i]\n",
    "        #             res = max(res, sum_value)\n",
    "        #         else:\n",
    "        #             sum_value = sum_list[n] - sum_list[i] + sum_list[(j+1)%n]\n",
    "        #             res = max(res, sum_value)\n",
    "        # return res\n",
    "        dp_max = [nums[0]]\n",
    "        dp_min = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            dp_max.append(max(dp_max[-1]+nums[i], nums[i]))\n",
    "            dp_min.append(min(dp_min[-1]+nums[i], nums[i]))\n",
    "        maxNums = max(dp_max)\n",
    "        minNums = min(dp_min)\n",
    "        sum_num = sum(nums)\n",
    "        if minNums == sum_num:\n",
    "            return maxNums\n",
    "        else:\n",
    "            return max(maxNums, sum_num - minNums)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        max_list=[]\n",
    "        min_list=[]\n",
    "        max_s = -inf  # 最大子数组和，不能为空\n",
    "        min_s = 0     # 最小子数组和，可以为空\n",
    "        max_f = min_f = 0\n",
    "        for x in nums:\n",
    "            # 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和\n",
    "            max_f = max(max_f, 0) + x\n",
    "            max_list.append(max_f)\n",
    "            # 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和\n",
    "            min_f = min(min_f, 0) + x\n",
    "            min_list.append(min_f)\n",
    "        max_s=max(max_list)\n",
    "        min_s=min(min_list)\n",
    "        if sum(nums) == min_s:\n",
    "            return max_s\n",
    "        return max(max_s, sum(nums) - min_s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        from itertools import accumulate\n",
    "        leftSums,rightSums = [],[]\n",
    "        pre,res = 0,-float(\"inf\")\n",
    "        leftSum,rightSum = 0,0\n",
    "        numsr = nums[::-1]\n",
    "        for i in range(len(nums)):\n",
    "            pre = pre + nums[i]\n",
    "            res = max(res,pre)\n",
    "            if pre < 0:\n",
    "                pre = 0\n",
    "            leftSum += nums[i]\n",
    "            if not leftSums:\n",
    "                leftSums.append(leftSum)\n",
    "            else:\n",
    "                leftSums.append(max(leftSum,leftSums[i-1]))\n",
    "            rightSum += numsr[i]\n",
    "            if not rightSums:\n",
    "                rightSums.append(rightSum)\n",
    "            else:\n",
    "                rightSums.append(max(rightSum,rightSums[i-1]))\n",
    "        rightSums = rightSums[::-1]\n",
    "        for i in range(1,len(nums)-1):\n",
    "            #print(leftSums[:i],rightSums[i:])\n",
    "            res = max(res,leftSums[i-1]+rightSums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        min_dp = [0] * len(nums)\n",
    "        max_dp = [0] * len(nums)\n",
    "        prefix = 0\n",
    "        min_dp[0] = nums[0]\n",
    "        max_dp[0] = nums[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            min_dp[i] = min(min_dp[i-1]+nums[i], nums[i])\n",
    "            max_dp[i] = max(max_dp[i-1]+nums[i], nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "        if max(max_dp) < 0:\n",
    "            return max(max_dp)\n",
    "        return max(max(max_dp), max([prefix-min_dp[i] for i in range(len(nums))]))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        prefix_sum = [0]\n",
    "        for i in range(2 * len(nums)):\n",
    "            prefix_sum.append(nums[i % len(nums)] + prefix_sum[-1])\n",
    "        \n",
    "        mq = deque()\n",
    "        max_sum = nums[0]\n",
    "\n",
    "        for i in range(len(prefix_sum)):\n",
    "            if mq and i - mq[0] > len(nums):\n",
    "                mq.popleft()\n",
    "            if mq and (curt := prefix_sum[i] - prefix_sum[mq[0]]) >= max_sum:\n",
    "                max_sum = curt\n",
    "            while mq and prefix_sum[i] <= prefix_sum[mq[-1]]:\n",
    "                mq.pop()\n",
    "            mq.append(i)\n",
    "        return max_sum\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums += nums\n",
    "        s = [0] + list(accumulate(nums))\n",
    "        ans = -inf\n",
    "        # 子数组最长为n\n",
    "        # 枚举右端点, s中寻找[r - n,r - 1]区间的最小值作为左端点，\n",
    "        # 这样s[r] - s[l]最大，考虑单调队列\n",
    "        q = deque([0])\n",
    "        ans = -inf\n",
    "        for r in range(1,2*n + 1):\n",
    "           \n",
    "            if q and r - q[0] > n:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans,s[r] - s[q[0]])\n",
    "            while q and s[q[-1]] >= s[r]:\n",
    "                q.pop()\n",
    "            q.append(r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        prefix_sum = [0]\n",
    "        for num in nums + nums:\n",
    "            prefix_sum.append(num + prefix_sum[-1])\n",
    "        \n",
    "        mq = deque()\n",
    "        max_sum = nums[0]\n",
    "\n",
    "        for i in range(len(prefix_sum)):\n",
    "            if mq and i - mq[0] > len(nums):\n",
    "                mq.popleft()\n",
    "            if mq and (curt := prefix_sum[i] - prefix_sum[mq[0]]) >= max_sum:\n",
    "                max_sum = curt\n",
    "            while mq and prefix_sum[i] <= prefix_sum[mq[-1]]:\n",
    "                mq.pop()\n",
    "            mq.append(i)\n",
    "        return max_sum\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        prefix_sum = [0]\n",
    "        for num in nums + nums:\n",
    "            prefix_sum.append(num + prefix_sum[-1])\n",
    "        \n",
    "        mq = deque()\n",
    "        max_sum = nums[0]\n",
    "\n",
    "        for i in range(len(prefix_sum)):\n",
    "            if mq and i - mq[0] > len(nums):\n",
    "                mq.popleft()\n",
    "            if mq and (curt := prefix_sum[i] - prefix_sum[mq[0]]) >= max_sum:\n",
    "                max_sum = curt\n",
    "            while mq and prefix_sum[i] <= prefix_sum[mq[-1]]:\n",
    "                mq.pop()\n",
    "            mq.append(i)\n",
    "        return max_sum\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
